package leetcode;

/**
 172. 阶乘后的零
 给定一个整数 n，返回 n! 结果尾数中零的数量。
 示例 1:
 输入: 3
 输出: 0
 解释: 3! = 6, 尾数中没有零。
 示例 2:
 输入: 5
 输出: 1
 解释: 5! = 120, 尾数中有 1 个零.
 */

public class problems_172 {

    public static void main(String[] arge) {
        System.out.println(new Solution().trailingZeroes(3));
    }

    static class Solution {
        /**
         * 思路，首先，先计算阶乘再看末尾的零的数量肯定是可以的，但是慢
         *
         * 那么,0是什么，0就说明阶乘过程中有10，几个10就是末尾有几个零
         * 而10的组成是2*5
         *   0! = 1
         *   1! = 1
         *   2! = 2^1 * 5^0 * 1
         *   3! = 2^1 * 5^0 * 3
         *   4! = 2^3 * 5^0 * 3
         *
         *   5! = 2^3 * 5^1 * 3
         *   6! = 2^4 * 5^1 * 3^2
         *   7! = 2^4 * 5^1 * x
         *   8! = 2^7 * 5^1 * x
         *   9! = 2^7 * 5^1 * x
         *
         *   10! = 2^8 * 5^2 * x
         *   11! = 2^8 * 5^2 * x
         *   12! = 2^10 * 5^2 * x
         *   13! = 2^10 * 5^2 * x
         *   14! = 2^11 * 5^2 * x
         *
         *   15! = 2^11 * 5^3 * x
         *   16! = 2^15 * 5^3 * x
         *
         *   所以，最终要判断的就是包含5的数量（2的数量肯定多余5的）
         */
        public int trailingZeroes(int n) {
            int count = 0;
            while (n > 0){
                count += (n/5);
                n /= 5;
            }
            return count;
        }
    }
}